/*
 * @lc app=leetcode.cn id=746 lang=golang
 *
 * [746] 使用最小花费爬楼梯
 */
package Solutions

// @lc code=start
func minCostClimbingStairs(cost []int) int {
	cache := make([]int, len(cost))
	for i := range cache {
		cache[i] = -1
	}
	var dfs func(i int) int
	dfs = func(i int) int {
		if i >= len(cache) {
			return 0
		}
		if cache[i] != -1 {
			return cache[i]
		}
		cache[i] = min_746(dfs(i+1), dfs(i+2)) + cost[i]
		return cache[i]
	}
	return min_746(dfs(0), dfs(1))
}
func min_746(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

// @lc code=end
